package cn.njupt;

import cn.njupt.printer.BinaryTreeInfo;
import java.util.Comparator;

public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {
    private E[] elements;

    public static final int DEFAULT_CAPACITY=10;

    //批量建堆
    public BinaryHeap(E[] elements,Comparator comparator){
        super(comparator);
        if(elements==null || elements.length==0){
            this.elements=(E[]) new Object[DEFAULT_CAPACITY];
        }else{
            int capacity=Math.max(DEFAULT_CAPACITY,elements.length);
            E[] newElements=(E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                newElements[i]=elements[i];
            }
            this.elements=newElements;
            this.size=elements.length;
            //批量建堆
            heapify();
        }

    }


    public BinaryHeap(E[] elements){
        this(elements,null);
    }


    public BinaryHeap(Comparator comparator){
        this(null,comparator);
    }

    public BinaryHeap(){
        this(null,null);
    }

    private  void heapify(){
        //自下而上的下滤
        for (int i = (size>>1)-1; i >=0; i--) {
            siftDown(i);
        }
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i]=null;
        }
        size=0;
    }

    @Override
    public void add(E element) {
        elementIsNull(element);
        //确保有size+1的容量
        ensureCapacity(size+1);
        elements[size++]=element;
        //专业名词叫做上虑
        siftUp(size-1);
    }

    /**
     * 插入元素
     * @param index 元素所在的索引，但是写的并不好，需要进行优化，因为每次都进行交换，可以只交换一次
     */
    /*private void siftUp(int index) {
//        index指的是当前插入数组中元素的索引
        while(index>0){
            int pIndex=(index-1)>>1;
            E p=elements[pIndex];
            E element=elements[index];
            if(compare(element,p)<=0)return;

            E temp=element;
            element=p;
            p=temp;

            index=pIndex;
        }
    }*/

    /**
     * 上滤
     * @param index
     */
    private void siftUp(int index){
        E newElement=elements[index];
        while(index>0){
            int pIndex=(index-1)>>1;
            E p=elements[pIndex];
            if(compare(newElement,p)<=0)break;

            elements[index]=p;
            index=pIndex;
        }
        elements[index]=newElement;
    }




    private void ensureCapacity(int capacity) {
        int oldCapacity=elements.length;
        //容器容量足够
        if(capacity<=oldCapacity)return;

        //容器容量不够,扩容1.5倍
        int newCapacity=(oldCapacity>>1)+oldCapacity;
        E[] newElements=(E[])new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i]=elements[i];
        }
        elements=newElements;
    }

    @Override
    public E get() {
        elementIsEmpty();
        return elements[0];
    }

    @Override
    public E remove() {
        elementIsEmpty();
        E result=elements[0];

        int lastIndex=--size;
        E lastElement=elements[lastIndex];

        elements[0]=lastElement;
        siftDown(0);
        elements[lastIndex]=null;
        return result;
    }

    /**
     * 下滤
     * @param index
     */
    private void siftDown(int index) {
        //index应该小于非叶子节点的最后一个元素的下标索引
        int half=size>>1;
        E element=elements[index];
        while(index<half){
            int childIndex=(index<<1)+1;
            E child=elements[childIndex];

            int rightIndex=childIndex+1;
            if(rightIndex<size && compare(child,elements[rightIndex])<0){
                child=elements[childIndex=rightIndex];
            }

            if(compare(element,child)>=0)break;
            elements[index]=child;

            index=childIndex;
        }
        elements[index]=element;

    }

    @Override
    public E replace(E element) {
        E top=null;
        if(size==0){
            elements[size++]=element;
        }else{
            top=elements[0];
            elements[0]=element;
            siftDown(0);
        }
        return top;
    }

    public int compare(E e1,E e2){
        if(comparator!=null){
            return comparator.compare(e1,e2);
        }
        return ((Comparable)e1).compareTo(e2);
    }

    public void elementIsEmpty(){
        if(size==0){
            throw  new RuntimeException("没有元素");
        }
    }

    public void elementIsNull(E element){
        if(element==null){
            throw new IllegalArgumentException("传递的元素为空");
        }
    }


    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        int index=((int)node<<1)+1;
        return index<size?index:null;
    }

    @Override
    public Object right(Object node) {
        int index=((int)node<<1)+2;
        return index<size?index:null;
    }

    @Override
    public Object string(Object node) {
        return elements[(int)node];
    }
}
